The present invention relates to digital communication systems. In particular, the present invention relates to the decoding of a convolutionally encoded data symbol sequence in a digital communication system.
Various error detection and correction techniques are used to increase the reliability of a communication system. The techniques involve the encoding of the transmitted data symbol sequence and the decoding of the received encoded data symbol sequence.
One such encoding technique is channel encoding. Channel encoding involves the addition of carefully designed redundant information to the data symbol sequence being transmitted through the channel. The received encoded data symbol sequence on the receiver side is then decoded to obtain the original data symbol sequence. Convolutional coding is one such form of channel coding. Convolutional coding is used to introduce redundancies in the transmitted data. The transmitter sends convolutionally encoded data rather than the transmitted data across a noisy channel. The receiver receives the convolutionally encoded data symbol sequence along with the errors, and corrects these errors in the decoding process.
A convolutional code is a sequence of encoded symbols, which is generated by passing the information sequentially through a series of binary shift registers. For example, if a 1/r code rate convolutional coding is used, then each input bit is encoded into r bits of data. The encoded bits are generated using code word polynomials and a binary shift register defined by constraint length, K.
Once encoded, the resulting code is modulated and transmitted across the noisy channel. On the receiver side, the encoded data is demodulated before being decoded.
There are various algorithms for decoding convolutionally encoded data. The Viterbi algorithm is one such technique used in the art. The Viterbi algorithm decodes a convolutionally encoded data symbol sequence using the prior knowledge of the possible encoder state transitions from a given state to the next state. The prior knowledge is based on the dependence of a given data state on past data. The allowable state transitions can be represented using a trellis diagram. Each node in the trellis diagram denotes the state of a data symbol sequence at a point in time. The branches connecting the nodes denote the state transitions.
The Viterbi decoding process has three basic steps. In the first step, the received data symbol is processed to determine the Euclidean distance between the received data symbol sequence and all possible actual data symbol sequences that could result from a state transition from the present to a next state. This result is stored in a memory for use during the next step. The Euclidean distance computed also is referred to as the branch metric for the path. The branch metric computation provides a measurement of the likelihood that a given path from the present state to a next state is correct.
In the second step, the stored branch metric values for all possible state transitions are processed to determine an “accumulated distance” for each input path. The path with the minimum distance, i.e., maximum probability, is then selected as the survivor path. This step is known as Add-Compare-Select, or ACS. The ACS operation can be broken into two operations, the Add operation involving a path metric computation, and a Compare-Select operation. The path metric at a stage is the accumulation of the accumulated error metric resulting from previous branch metric computations and the branch metric values for a received data input symbol. The accumulated error metric values are computed from the Add operation, to determine and store the “trace-back bits” to indicate the selected survivor path.
The third step is known as trace-back. This step traces the maximum likelihood path through the trellis of state transitions, as determined by the first two steps, and reconstructs the most likely path through the trellis, to extract the original data input to the encoder.
Conventional implementations, for an encoder of code rate r, typically compute all 2^r branch metrics for a given data input symbol at any stage of a decoding process and store the entire branch metric set in memory. This technique requires a minimum of 2^r calculations, which consumes a large number of machine cycles. Further, storing the entire 2^r branch metrics uses a relatively large amount of memory. A large memory requirement together with a large number of machine cycles for decoding increases the power requirements of the decoder. Additionally, the die-area of the chip used to implement the decoder must be large to accommodate the large memory required.
Hence, there is a need for a method and system that reduces the computational complexity of the decoding technique, thereby reducing memory requirements and the system delay associated with the method of decoding. Further, there is a need for a method and system that reduces the power consumed in decoding the received data and for one that reduces the die-size of the chip implementing the decoder.